#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
class Partition {
public:
    ListNode* partition(ListNode* phead, int x) {
        struct ListNode* beforehead, * afterhead, * list1, * list2;
        beforehead = list1 = (struct ListNode*)malloc(sizeof(struct ListNode));
        afterhead = list2 = (struct ListNode*)malloc(sizeof(struct ListNode));

        while (phead)
        {
            if (phead->val < x)
            {

                list1->next = phead;
                list1 = list1->next;
            }
            else
            {

                list2->next = phead;
                list2 = list2->next;
            }
            phead = phead->next;
        }
        list1->next = afterhead->next;
        list2->next = NULL;
        struct ListNode* head = beforehead->next;
        free(beforehead);
        free(afterhead);

        return head;
    }

};
